/*************************************************************************
	> File Name: inorder_thread.cpp
	> Author: 
	> Mail: 
	> Created Time: Sun 28 Jul 2024 07:15:43 AM CST
 ************************************************************************/

#include<iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

typedef struct Node {
	int val;
	int ltag, rtag;
	struct Node *lchild, *rchild;
} Node;

Node *getNewNode(int val) {
	Node *p = (Node *)malloc(sizeof(Node));
	p->val = val;
	p->ltag = p->rtag = 0;
	p->lchild = p->rchild = nullptr;
	return p;
}

Node *insert(Node *root, int val) {
	if(root == nullptr) return getNewNode(val);
	if(root->val == val) return root;
	if(root->val > val) root->lchild = insert(root->lchild, val);
	else root->rchild = insert(root->rchild, val);
	return root;
}
void inOrder(Node *root) {
	if(root == nullptr)	return ;
	if(root->ltag == 0) inOrder(root->lchild);
	printf("%d-> ", root->val);
	if(root->rtag == 0) inOrder(root->rchild);
	return ;
}
void buildThread(Node *root) {
	if(root == nullptr) return ;
	static Node *pre_node = nullptr;
	if(root->ltag == 0) buildThread(root->lchild);
	if(root->lchild == nullptr) {
		root->lchild = pre_node;
		root->ltag = 1;
	}
	if(pre_node && pre_node->rchild == nullptr) {
		pre_node->rchild = root;
		pre_node->rtag = 1;
	}
	pre_node = root;
	if(root->rtag == 0) buildThread(root->rchild);
	return ;
}

Node *mostLeft(Node *root) {
	while(root && root->ltag == 0 && root->lchild != nullptr) {
		root = root->lchild;
	}
	return root;
}

void outPut(Node *root) {
	if(root == nullptr) return ;
	Node *p = mostLeft(root);
	while(p) {
		printf("%d-> ", p->val);
		if(p->rtag == 1) p = p->rchild;
		else p = mostLeft(p->rchild);
	}
	printf("\n\n");
	return ;
}
void clear(Node *root) {
	if(root == nullptr) return ;
	if(root->ltag == 0) clear(root->lchild);
	if(root->rtag == 0) clear(root->rchild);
	free(root);
	return ;
}
#define MAX_N 10
int main() {
	Node *root = nullptr;
	for(int i = 0; i < MAX_N; i++) {
		root = insert(root, rand() % 100);
	}
	inOrder(root);
	printf("\n\n");
	buildThread(root);
	outPut(root);
	clear(root);
	return 0;
}

